package com.my.study.test;

/**
 * @author: yidujun
 * @create: 2021/07/03 13:35
 */
public class FrogStepsDynamic {

    public static void main(String[] args) {
        System.out.println("===========动态规划=============");
        System.out.println(frogStepsByDynamic(3));
        System.out.println(frogStepsByDynamic(4));
        System.out.println("============递归============");
        System.out.println(frogStepsByRecursion(3));
        System.out.println(frogStepsByRecursion(4));
    }

    /**
     * 动态规划
     *
     * @param step 总台阶数
     * @return
     */
    private static int frogStepsByDynamic(int step) {
        if (step < 3) {
            return step;
        }
        // 1.定义dp含义，dp[i]代表跳i个台阶的跳法
        int[] dp = new int[step + 1];
        // 2.初始值
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;

        // 3.找关系
        for (int i = 3; i <= step; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[step];
    }

    /**
     * 递归
     *
     * @param step
     * @return
     */
    private static int frogStepsByRecursion(int step) {
        if (step <= 2) {
            return step;
        }
        return frogStepsByRecursion(step - 1) + frogStepsByRecursion(step - 2);
    }
}
